--- title: "4、测试次数" created: 2025-11-28 tags: - 算法 --- # 4、测试次数 ## 题目 [测试次数](https://www.lanqiao.cn/paper/3848/problem/616/) ![[image-9dd8f3af.png]] ## 思路分析 一开始以为直接二分就行了 算$log\_2^n $ 但是…… 如果一个手机的真正耐摔指数为6的话 而二分到了8 它就一定会被摔坏 这样并不能测出来它的耐摔指数 所以测试就得从下往上一个一个测 神特么最优策略 最坏运气 最多次数 题意模糊 **最坏的运气下所需的最少测试次数”** 是指在考虑所有可能的情况（包括最不利情况）之后，确定耐摔指数所必需的**最小测试次数**。这是一种优化问题，目的是找到最高效的测试策略，即在最坏情况下测试次数尽可能少。这种情况下的“最少”实际上指的是在所有可能的最坏情况下，我们能做到的最好结果。 **使用i台手机在高度为j的楼层测试所需的最多次数** 这样的表述可能会引导到一个略有不同的问题定义，可能意味着考虑一种非最优的策略下，进行测试可能达到的最大测试次数。但这并不是我们想要解决的问题。 ![[image-8c1b4615.png]] **状态表示** **索引**`i`：代表当前剩余可用于测试的手机数量。当一部手机在测试中摔坏时，剩余可用的手机数量减少。 **索引**`j`：代表当前考虑的楼层数范围。在问题开始时，`j`是整个楼的高度，随着测试的进行，`j`会根据测试结果调整，代表可能的耐摔楼层范围。 **值**`f[i][j]`：表示在最坏情况下，使用`i`部手机在高度为`j`的楼测试手机的耐摔性时，需要的最少测试次数。 **状态转移** 状态转移方程考虑了在当前状态下进行一次测试后的所有可能结果，选择这些结果中测试次数最多的一个作为当前状态的值，加上这一次测试，就是`f[i][j]`的值。具体来说： 当在某一楼层`x`进行测试时，有两种可能的结果：手机摔坏或没坏。 **如果手机摔坏**：我们失去了一部手机（手机数量从`i`减少到`i-1`），同时楼层的可能范围缩小到`x-1`层以下（因为我们知道`x`层能摔坏手机，所以耐摔指数在`x-1`层或更低）。这对应于状态`dp[i-1][x-1]`。 **如果手机没坏**：手机数量保持不变，但我们知道耐摔指数至少是`x`，因此楼层的可能范围缩小到`j-x`层（在`x+1`到`j`之间）。这对应于状态`dp[i][j-x]`。 因此，我们对每一种可能的测试楼层`x`（从1到`j`）计算以上两种情况的最大值（因为我们考虑的是最坏情况），并在所有楼层`x`中找到这个最大值最小的情况。最后，`f[i][j]`就是这个最小的最大值加上这次测试（因此有`1 + max(dp[i-1][x-1], dp[i][j-x])`）。 这题的状态表示和状态转移…… 确实有点难想 ## 代码实现 ```cpp #include using namespace std; const int N=1010; int f[N][N]; int main() { int k=3,n=1000; memset(f,0,sizeof f); for(int i=1;i<=n;i++){ f[1][i]=i;//一台手机 无所谓策略 最坏情况下测试次数就是楼层数 } for(int i=2;i<=k;i++){//枚举手机 for(int j=1;j<=n;j++){//枚举楼层 f[i][j]=0x3f3f3f; for(int x=1;x<=j;x++){//1-j层找最优 //没坏 往上找 j-x 坏了 往下找 x-1 int cost=max(f[i][j-x],f[i-1][x-1])+1; f[i][j]=min(cost,f[i][j]); } } } cout<